package leetcode4;
import java.util.*;
public class Day1 {


    /**
     * n叉树的层序遍历
     * @param root
     * @return
     */
    /*public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root==null) return ret;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for(int i=0;i<size;i++) {
                Node tmp = queue.poll();
                list.add(tmp.val);
                List<Node> nodes = tmp.children;
                for(Node n:nodes) {
                    queue.add(n);
                }
            }
            ret.add(list);
        }
        return ret;
    }*/


    public int subarraySum(int[] nums, int k) {
        int ret=0;
        Map<Integer,Integer> map = new HashMap<>();//k:前缀和  v:该前缀和出现的次数
        map.put(0,1);
        int sum=0; // 记录前缀和
        for(int i=0;i<nums.length;i++) {
            sum += nums[i];
            //假设存储在map中的一个前缀和为dp[j],那么是否存在dp[i]-dp[j]==k呢？（j<i）
            if(map.containsKey(sum-k)) {
                ret += map.get(sum-k);
            }
            map.put(sum,map.getOrDefault(sum,0)+1);
        }
        return ret;
    }






}
